package com.atcumt.lcSolution;

import java.util.HashMap;
import java.util.Map;

public class LC5 {

    /**
     * 旋转字符串
     * <p>
     * 每次旋转操作都是将最左侧字符移动到最右侧，因此如果 goal 可由 s 经过多步旋转而来，
     * 那么 goal 必然会出现在 s + s 中，同时我们还要确保两字符串长度相等
     */
    public boolean rotateString(String s, String goal) {
        return s.length() == goal.length() && (s + s).contains(goal);
    }

    /**
     * 最小覆盖子串
     */
    public String minWindow(String s, String t) {

        // t 中字符全放到 Map 中
        Map<Character, Integer> map = new HashMap<>();
        for (char str : t.toCharArray()) {
            map.put(str, map.getOrDefault(str, 0) + 1);
        }

        int start = 0, left = 0, right = 0, windowSize = Integer.MAX_VALUE;
        while (right < s.length()) {
            char rightScan = s.charAt(right);
            if (map.containsKey(rightScan)) {
                map.put(rightScan, map.getOrDefault(rightScan, 0) - 1); // s 中包含 t中字符, -1操作
            }
            right++;

            // 维护滑动窗口
            while (check(map)) {
                if (right - left < windowSize) {
                    start = left;
                    windowSize = right - left;
                }

                // 缩小窗口
                char leftScan = s.charAt(left);
                if (map.containsKey(leftScan)) {
                    map.put(leftScan, map.getOrDefault(leftScan, 0) + 1);
                }
                left++;
            }
        }
        if (windowSize != Integer.MAX_VALUE) {
            return s.substring(start, start + windowSize);
        }
        return "";
    }

    /**
     * 检查窗口是否把字符串 t中所有的字符都覆盖，如果map中有，value值都不大于零表示全覆盖
     * value可以为负数，比如窗口字符"ABBC"
     */
    private boolean check(Map<Character, Integer> map) {
        for (int value : map.values()) {
            if (value > 0) {
                return false;
            }
        }
        return true;
    }
}
